package com.cdream.basic.algorithm.leetcode.findElement;

import java.util.TreeSet;

/**
 * todo 桶排序
 *
 * @author cdream
 * @date 6/6/21
 */
public class Question220 {
    public static void main(String[] args) {
        System.out.println(new Question220().containsNearbyAlmostDuplicate(new int[]{1, 5, 9, 1, 5, 9}, 2, 3));
    }

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> set = new TreeSet<>();

        for (int i = 0; i < nums.length; i++) {
            Long num = (long) nums[i];
            Long ceiling = set.ceiling(num - t);
            if (ceiling != null && ceiling <= num + t) {
                return true;
            }
            set.add(num);
            if (set.size() >= k + 1) {
                set.remove((long)nums[i - k]);
            }
        }
        return false;
    }
}
